package leetcode;

import java.util.Arrays;
import java.util.HashMap;

/*
2 <= nums.length <= 500
0 <= nums[i] <= 100
 */
public class Test1365 {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        /*
        1.创建长度为101的桶
        2.在桶对应的位置记录每个数字出现的次数 一次遍历-计数排序
        3.遍历桶，用HashMap记录累计出现的比它小的次数 二次遍历
        4.遍历数组，给出结果 三次遍历
        时间复杂度N（o）
        边界条件：都是 1 结果都是0
         */
        int[] bucket=new int[101];
        for(int a:nums){
            bucket[a]++;
        }
        int sum=0;
        for(int i=0;i<bucket.length;i++){
            int tmp=bucket[i];
            bucket[i]=sum;
            sum=sum+tmp;
        }
        for(int i=0;i<nums.length;i++){
            nums[i]=bucket[nums[i]];
        }
        return nums;
    }
}
